/* 
	这个版本的头节点无数据,待解决
*/
#include <stdio.h>
#include <stdlib.h> 
#include <time.h> 

typedef struct list* link; 
struct list{
	int data;
	struct list *next;
};//终于解决了，原来问题在于C语言中对结构严格要求，即使用必须加struct

struct list *initialList(){	//是否可以在外面初始化头节点
	struct list *head = (struct list *)malloc(sizeof(struct list));
	head -> next = NULL;
//	head -> data = 'A';//头节点无数据可以注释掉
	return head;
}

void printListEle(struct list *head, int nul){
	struct list *temp = head -> next;//头节点只起标记作用
	//list *temp = head;//头节点又数据
	while (--nul){ 
		temp = temp -> next;
	}
	printf("%d \n",temp -> data);
}
		
void addList(struct list *head, int nul, int in){
	struct list *temp = head; 
	while(--nul){
			temp = temp -> next;  
  	}
	struct list *qemp = (struct list *)malloc(sizeof(struct list));
	qemp -> data = in;
 	qemp -> next = temp -> next;
 	temp -> next = qemp;
}
	
void printList(struct list *head){
	struct list *temp = head -> next;
	do{
		printf("%d ", temp -> data);
		temp = temp -> next;
	}while(temp);
	printf("\n");
}

void deleteListEle(struct list *head, int nul){
	struct list *temp = head;
		while(--nul){
			temp = temp  -> next;
 			}
	struct list *qemp = temp -> next;
		temp -> next = qemp -> next;
		free(qemp);
}

void deleteList(struct list *head){
	struct list *temp = head -> next;
	do{
		head -> next = temp -> next;
		free(temp);
		temp = head -> next;
	}while(temp);	//出现了溢出
}
void reverseList(struct list *head){
	
	link t = head->next, td = NULL, pt;
	while(t != NULL){
		pt = t->next;
		t->next = td;
		td = t;
		t = pt;
	}
	head->next = td;
}
/*
void sortList(struct list *head){
	link h1 = head->next, th;
	if(h1 == NULL) return ;
	struct list *h1n1= (struct list *)malloc(sizeof(struct list));
	h1n1->next = NULL;
	while(h1 != NULL){
		link insert = h1;
		th = h1n1;
		h1 = insert->next;
		while(th->next !=NULL && th->next->data > insert->data)
			th = th->next;
		insert->next = th->next;
		th->next = insert;
	}
	head->next = h1n1->next;
}*/

/*void sortList(link head){
	link h1 = head->next, h2;
	struct list *h1n1 = (struct list*)malloc(sizeof(struct list));
	h1n1->next = NULL;
	while(h1 != NULL){
		link insert = h1;
		h1 = h1->next;
		h2 = h1n1;
		while(h2->next != NULL && h2->next->data > insert->data)
				h2 = h2->next;
		insert->next = h2->next;
		h2->next = insert;  
	}
	head->next = h1n1->next;	
}
*/

void sortList(link head){
	link h1 = head->next, h2;
	struct list *h1n1 = (struct list *)malloc(sizeof(struct list));
	h1n1->next  = 	NULL;
	while(h1 != NULL){
		link insert = h1;
		h1 = insert->next;
		h2 = h1n1;
		while(h2->next != NULL && h2->next->data > insert->data)
			h2 = h2->next;
		insert->next = h2->next;
		h2->next = insert; 
	}
	head->next = h1n1->next;

}
void mergeList(link head1, link head2){
	link h2 = head2->next, h1;
	while(h2 != NULL){
		link insert = h2;
		h2 = insert->next;
		h1 = head1; 
		while(h1->next != NULL && h1->next->data > insert->data)
			h1 = h1->next;
		insert->next = h1->next;
		h1->next = insert;			
	}
}

int 
main(){
	srand(time(NULL));
//	list *head = (list *)malloc(sizeof(list));
	struct list *head1 = initialList();
	struct list *head2 = initialList();
	int i;	
	for(i = 0; i < 10; i++){
		addList(head1, 1,random() % 100);
		addList(head2, 1,random() % 100);
	}
//	printListEle(head, 2);
	printList(head1);
	printList(head2);
//	reverseList(head);	
//	deleteListEle(head, 2);
	sortList(head2);
	sortList(head1);
	printList(head1);
	printList(head2);
	mergeList(head1, head2);
	printList(head1);
//	deleteList(head);
//	printListEle(head, 1);
}


